/*
解题思路：
 1. 从前序遍历结果中获取到树的根节点
 2. 在中序遍历结果中确定根节点的位置，按照该位置将中序遍历结果分为两部分
    左半部分是根节点的左子树，递归创建根节点的左子树
    右半部分是根节点的右子树，递归创建根节点的右子树
*/
class Solution3 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTree(preorder, inorder, 0, inorder.length);
    }


    // index不断在前序遍历中找根节点，每次找完之后，根据找到的根节点将中序遍历分成左右两部分，左侧为根的左子树，右侧为根的右子树
    int index = 0;
    private TreeNode buildTree(int[] preorder, int[] inorder, int left, int right){
        if(left >= right){
            return null;
        }
        // 创建跟节点
        TreeNode root = new TreeNode(preorder[index]);
        // 在中序遍历结果中找到根的位置
        int rootIdx = left;
        while(rootIdx < right){
            if(inorder[rootIdx] == preorder[index])
                break;

            rootIdx++;
        }
        index++;
        //[left, rootIdx)：左子树中的所有节点
        // 递归创建根的左子树
        root.left = buildTree(preorder, inorder, left, rootIdx);
        //[rootIdx+1, right): 右子树中的所有节点
        // 递归创建根的右子树
        root.right = buildTree(preorder, inorder, rootIdx+1, right);
        return root;
    }
}